class Solution
{
public:
    // f[i]: 表示以i位置为结尾的序列的最长回文子串的长度
    // 找到前面相同的字符j，然后从f[i - 1]找到f[j + 1]看f[j + 1][i - 1]的最长子串
    //
    int longestPalindromeSubseq(string s)
    {
        vector<vector<int>> f(s.size(), vector<int>(s.size()));
        int res = 1;
        for (int len = 1; len <= s.size(); ++len)
        {
            for (int l = 0; l + len - 1 < s.size(); ++l)
            {
                int r = l + len - 1;
                if (l == r)
                    f[l][r] = 1;
                else if (l == r - 1)
                    f[l][r] = s[l] == s[r] ? 2 : 1;
                else
                {
                    if (s[l] == s[r])
                        f[l][r] = max(max(f[l][r - 1], f[l + 1][r]), f[l + 1][r - 1] + 2);
                    else
                        f[l][r] = max(max(f[l][r - 1], f[l + 1][r]), f[l + 1][r - 1]);
                }
                res = max(res, f[l][r]);
            }
        }
        return res;
    }
};